//题目:
// 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
// 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
// 网格中的障碍物和空位置分别用 1 和 0 来表示。
#include<iostream>
#include<vector>
#include<map>

using namespace std;
//代码
class Solution 
{
    int ret=0;
    int dx[2]={0,1},dy[2]={1,0};//方向矢量:右、下
    // map<pair<int,int>,int> dp;//记录从(i,j)位置出发，到达终点的路径数目
public:
    //1.全排列
    // void dfs(const vector<vector<int>>& obstacleGrid,int row,int col)
    // {
    //     if(row==obstacleGrid.size()-1 && col==obstacleGrid[0].size()-1 && obstacleGrid[row][col]!=1)
    //     {
    //         ret++;
    //         return;
    //     }
    //     //寻找下一个落脚点
    //     for(int i=0;i<2;i++)
    //     {
    //         int x=row+dx[i],y=col+dy[i];
    //         if(x>=0 && x<obstacleGrid.size() && y>=0 && y<obstacleGrid[0].size() && obstacleGrid[x][y]!=1)
    //         {
    //             dfs(obstacleGrid,x,y);
    //         }
    //     }
    // }

    //2.记忆化搜索
    // int dfs(const vector<vector<int>>& obstacleGrid,int row,int col)
    // {
    //     if(row==obstacleGrid.size()-1 && col==obstacleGrid[0].size()-1 && obstacleGrid[row][col]!=1)
    //         return 1;
        
    //     if(dp.count({row,col}))return dp[{row,col}];

    //     int count=0;//记录从(row,col)到终点的路径数目
    //     //寻找下一个落脚点
    //     for(int i=0;i<2;i++)
    //     {
    //         int x=row+dx[i],y=col+dy[i];
    //         if(x>=0 && x<obstacleGrid.size() && y>=0 && y<obstacleGrid[0].size() && obstacleGrid[x][y]!=1)
    //             count+=dfs(obstacleGrid,x,y);
    //     }

    //     dp[{row,col}]=count;
    //     return count;
    // }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        if(obstacleGrid[0][0]==1)return 0;
        //法一：全排列————超时
        // dfs(obstacleGrid,0,0);
        // return ret;

        //法二：优化————记忆化搜索
        // return dfs(obstacleGrid,0,0);

        //法三：动态规划
        //1.创建dp表————记录从(0,0)位置出发，到达(i,j)的路径数目
        map<pair<int,int>,int> dp;
        //2.初始化
        bool flag=false;
        for(int i=0;i<obstacleGrid.size();i++)
        {
            if(obstacleGrid[i][0]==1 || flag==true)
            {
                dp[{i,0}]=0;
                flag=true;
            }
            else 
                dp[{i,0}]=1;
        }
        flag=false;
        for(int j=0;j<obstacleGrid[0].size();j++)
        {
            if(obstacleGrid[0][j]==1 || flag==true)
            {
                dp[{0,j}]=0;
                flag=true;
            }
            else 
                dp[{0,j}]=1;
        }
        //3.填表
        for(int i=1;i<obstacleGrid.size();i++)
        {
            for(int j=1;j<obstacleGrid[0].size();j++)
            {
                if(obstacleGrid[i][j]==1)
                    dp[{i,j}]=0;
                else 
                    dp[{i,j}]=dp[{i-1,j}]+dp[{i,j-1}];
            }
        }
        //4.确定返回值
        return dp[{obstacleGrid.size()-1,obstacleGrid[0].size()-1}];
    }
};